The present invention relates to a method for efficient list decoding of Reed Solomon codes and sub-codes thereof
Algebraic geometric (AG) codes utilizing the algebraic curve theory have been developed. Reed Solomon (RS) codes are well known as a subclass of error correction AG codes for correcting errors produced in a communication channel or a storage medium at the reception side in a digital communication system and a digital storage system. The codes have been used for example in devices which deal with compact disc and satellite communication systems.
Reed-Solomon codes are defined in terms of Galois or finite field arithmetic. Both the information and the redundancy portions of such codes are viewed as consisting of elements taken from some particular Galois field. A Galois field is commonly identified by the number of elements which it contains. The elements of a Galois field may be represented as polynomials in a particular primitive field element, with coefficients in the prime subfield. The location of errors and the true value of the erroneous information elements are determined after constructing certain polynomials defined on the Galois field and finding the roots of these polynomials. Since the number of elements contained in a Galois field is always equal to a prime number, q, raised to a positive integer power, m, the notation, GF(qm) is commonly used to refer to the finite field containing qm elements. In such a field all operations between elements comprising the field, yield results which are each elements of the field.
Decoding methods for RS and AG codes have been described, for example, decoding methods have been described which decode RS codes and AG codes up to a designed error correction bound, such as the error-correction bound (dxe2x88x921)/2 of the code in which d is the minimum distance of the code. See G. L. Feng and T. R. N. Rao, xe2x80x9cDecoding Algebraic-geometric Codes up to the Designed Minimum Distance,xe2x80x9d IEEE Trans. Inform. Theory, 39:37-45, 1993.
List decoding algorithms have been developed to provide decoding of RS codes beyond the error correction bound. Given a received encoded word and an integer l, this algorithm returns a list of a size at most l of codewords which have distance at most e from the received word, where e is a parameter depending on l and the code. See M. Sudan, xe2x80x9cDecoding of Reed-Solomon Codes Beyond the Error-correction Bound,xe2x80x9d J. Compl., 13:180-193, 1997. List decoding has been extended to AG codes using an interpolation scheme and factorization of polynomials over algebraic function fields in polynomial time. See M. A. Shokrollahi and H. Wasserman, xe2x80x9cList Decoding of Algebraic-geometric Codesxe2x80x9d, IEEE Trans. Inform. Theory, 45:432-437, 1999. The list decoding process for AG codes consists of a first step of computing a non-zero element in the kernel of a certain matrix and a second step of a root finding method. It is desirable to provide an improved method for efficient list decoding of RS codes and subcodes thereof.
The present invention relates to a method and apparatus for efficient list decoding of Reed-Solomon error correction codes. A polynomial for a predetermined target list size combining points of an error code applied to a message and points of a received word is determined for a k dimensional error correction code by a displacement method. The displacement method finds a nonzero element in the kernel of a structured matrix which determines the polynomial. From roots of the polynomial, it is determined if the number of errors in the code word is smaller than a predetermined number of positions for generating a list of candidate code words meeting the error condition. In one embodiment, parallel processing is used for executing the displacement method. The invention will be more fully described by reference to the following drawings.